package club.xiaojiawei.hash;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 4/28/22 5:41 PM
 * @question 438.找到字符串中所有字母异位词
 * @description 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 */
public class FindAllStr438 {

    public static void main(String[] args) {
        System.out.println((int)'a');
        String s1 = "cbaebabacd";
        String s2 = "abc";
        List<Integer> result = findAnagrams3(s1, s2);
        result.forEach(System.out::println);
    }

    /**
     * 滑动窗口法
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        int[] table = getCount(p);
        int[] exist = getCount(p);
        int surplus = p.length();
        ArrayList<Integer> list = new ArrayList<>();
        int t;
        for (int i = 0; i < s.length();i++) {
            if (table[t =s.charAt(i) - 'a'] != 0){
                table[t]--;
                surplus--;
                if (surplus == 0){
                    list.add(t = i - p.length() + 1);
                    table[s.charAt(t) - 'a']++;
                    surplus++;
                }
            }else if (exist[t] == 0){
                surplus = p.length();
                table = getCount(p);
            }else {
                int temp = i - p.length() + surplus;
                while (temp < i && s.charAt(temp) != s.charAt(i)){
                    table[s.charAt(temp++) - 'a']++;
                }
                surplus = temp - i + p.length();
            }
        }
        return list;
    }

    /**
     * 暴力解法
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams2(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        int[] table = getCount(p);
        int count = p.length();
        for (int i = 0; i < s.length(); i++) {
            if (count != p.length()){
                table = getCount(p);
                count= p.length();
            }
            for (int j = i; j<s.length(); j++){
                if (table[s.charAt(j) - 'a'] != 0){
                    table[s.charAt(j) - 'a']--;
                    count--;
                }else {
                    break;
                }
                if (count == 0){
                    list.add(j - p.length() + 1);
                    break;
                }
            }
        }
        return list;
    }

    /**
     * 民间-双指针(nb)
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams3(String s, String p) {
        int[] count = new int[26];
        for (char c : p.toCharArray()) {
            count[c - 'a']++;
        }
        int slow = 0, fast = 0;
        char[] chars = s.toCharArray();
        List<Integer> res = new ArrayList<>();
        while (fast < chars.length) {
            if (count[chars[fast] - 'a'] != 0) {
                count[chars[fast++] - 'a']--;
                if (fast - slow == p.length()) {
                    res.add(slow);
                }
            } else {
                count[chars[slow++] - 'a']++;
            }
        }
        return res;
    }

    /**
     * 滑动窗口+hash
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams4(String s, String p) {
        if (s.length() < p.length()){
            return new ArrayList<>();
        }
        int[] hash = new int[123];
        char[] chars = p.toCharArray();
        for (char aChar : chars) {
            hash[aChar]++;
        }
        char[] array = s.toCharArray();
        ArrayList<Integer> result = new ArrayList<>();
        int slow = -1, fast = -1, count = 0;
        while (++fast < s.length()){
            if (hash[array[fast]] == 0){
                while (++slow < fast && array[slow] != array[fast]){
                    hash[array[slow]]++;
                    count--;
                }
            }else {
                hash[array[fast]]--;
                if (++count == p.length()){
                    hash[array[++slow]]++;
                    result.add(slow);
                    count--;
                }
            }
        }
        return result;
    }

    public static int[] getCount(String s){
        int[] ints = new int[26];
        for (int i = 0; i < s.length(); i++) {
            ints[s.charAt(i) - 'a']++;
        }
        return ints;
    }
}
